Demystifying Latschev’s Theorem

SoCG 2024

Sush Majhi
George Washington University, USA

Today’s Agenda

  • The problem of shape reconstruction
  • Vietoris–Rips complexes
  • Theorems of Hausmann and Latschev
  • Demystifying Latschev’s theorem
    • Jung’s theorem on manifolds
    • Sketch of proof (if time permits)
  • Questions

The Problem of Shape Reconstruction

  • Shape: A Shape is modeled as a metric space \((M,d_M)\).

    • general compact set

    • metric graph

    • for today, \(M\) is a closed Riemannian manifold.

  • Sample: A finite metric space \((X,d_X)\) close to \(M\).

    • small Hausdorff proximity if \(M\) is a Euclidean submanifold and \(X\subset\mathbb R^d\)

    • for today, small Gromov–Hausdorff distance.

  • Goal: Infer the topology of \(M\) from \(X\).

    • Estimate only the Betti numbers: number of connected components, cycles, voids, etc, of \(M\).

    • for today, construct a topological space \(\widetilde{M}\) from \(X\) to retain the topology of \(M\), i.e., \(M\simeq\widetilde{M}\).

Vietoris–Rips Complex

  • a metric space \((X,d_X)\)

  • a scale \(\beta>0\)

  • \(\mathcal{R}_\beta(X)\) is an abstract simplicial complex such that

    • each subset \(A\subset X\) of size \(k\) with diameter at most \(\beta\) is a \((k-1)\)-simplex.

Hausmann’s Theorem

Convexity Radius

  • the largest (sup) radius so that geodesic balls are convex.

    • for the circle, it is a quarter of the circumference

    • denoted by \(\rho(M)\)

    • \(\rho(M)>0\) for a compact manifold

Theorem (Hausmann 1995): For any \(0<\beta<\rho(M)\), the Vietoris–Rips complex \(\mathcal{R}_\beta(M)\) is homotopy equivalent to \(M\).

  • vertex set is the entire manifold \(M\)
  • Question: what about the Vietoris–Rips complex of a dense subset \(X\subset M\)?
    • more generally, for a sample with a small \(d_{GH}(M,X)\).

Finite Reconstruction Problem

Gromov–Hausdorff Distance:

  • provides the noise model for our reconstruction problem
  • similarity measure between abstract metric spaces \((X,d_X)\) and \((Y,d_Y)\)
  • Definition: \(d_{GH(X,Y)}=\inf d_H^Z(f(X),g(Y))\)
    • inf over metric spaces \((Z,d_Z)\) and isometries \(f:X\to Z\), \(g:Y\to Z\)

See Adams et al. (2023) for more details on the relation between the Gromov–Hausdorff and Hausdorff distances.

Demystifying Latschev’s Theorem

Latschev’s Theorem (Latschev 2001):

For every closed Riemannian manifold \(M\), there exists a positive number \(\epsilon_0\) such that for any \(0<\beta\leq\epsilon_0\) there exists some \(\delta>0\) such that for every metric space \(X\) with Gromov–Hausdorff distance to \(M\) less than \(\delta\), the Vietoris–Rips complex \(\mathcal R_\beta(X)\) is homotopy equivalent to \(M\).

Key points:

  • The result is qualitative

  • the threshold \(\epsilon_0=\epsilon_0(M)\) depends solely on the geometry of \(M\). But the theorem did not say how!

  • \(\delta=\delta(\beta)\) is a function (probably a fraction) of \(\beta\).

  • Nonetheless, the result answers Hausmann’s question!

Quantitative Latschev’s Theorem

Metric Graph Reconstruction (Majhi 2023b)

Let \((G,d_G)\) be a compact, path-connected metric graph, \((X,d_X)\) a metric space, and \(\beta>0\) a number such that \[3d_{GH}(G,X)<\beta<3\rho(G)/4.\] Then, \(\mathcal R_\beta(X)\simeq G\).

Key points:

  • The result is quantitative

  • \(\epsilon_0=3\rho(G)/4\)

  • \(\delta=\beta/3\)

Quantitative Latschev’s Theorem

Riemannian Manifold Reconstruction (Majhi 2023a)

Let \((M,d_M)\) be a closed, connected Riemannian manifold. Let \((X,d_X)\) be a compact metric space and \(\beta>0\) a number such that \[ \frac{1}{\zeta}d_{GH}(M,X)<\beta<\frac{1}{1+2\zeta}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\} \] for some \(0<\zeta\leq1/14\). Then, \(\mathcal R_\beta(X)\simeq M\).

Key points:

  • \(\kappa\) is an upper bound on the sectional curvatures of \(M\)

  • For \(\zeta=\frac{1}{14}\):

    • \(\epsilon_0=\frac{7}{8}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\}\)

    • \(\delta=\frac{\beta}{14}\)

Quantitative Latschev’s Theorem

Euclidean Submanifold Reconstruction (Majhi 2023a)

Let \(M\subset\mathbb R^N\) be a closed, connected submanifold. Let \(X\subset\mathbb R^N\) be a compact subset and \(\beta>0\) a number such that \[ \frac{1}{\zeta}d_{H}(M,X)<\beta<\frac{3(1+2\zeta)(1-14\zeta)}{8(1-2\zeta)^2}\tau(M) \] for some \(0<\zeta<1/14\). Then, \(\mathcal R_\beta(X)\simeq M\).

Key points:

  • \(\tau(M)\) is the reach of \(M\)

  • For \(\zeta=\frac{1}{28}\):

    • \(\epsilon_0=\frac{315}{1352}\tau(M)\)

    • \(\delta=\frac{\beta}{28}\)

Jung’s Theorem

For a compact set \(A\subset\mathbb R^n\), there exists a unique circumcenter, and the circumradius \(\mathfrak{R}(A)\) is at most \(\sqrt{\frac{n}{2(n+1)}}\) times the diameter of \(A\).

Manifold: (Dekster 1997) Let \(M\) be a compact, connected, \(n\)–dimensional manifold. For any compact subset \(A\) with \(diam(A)<\min\{\rho(M),\pi/4\sqrt{\kappa}\}\), its circumcenter exists in \(M\). Moreover, its diameter \[\begin{equation}\label{eqn:Jung} diam(A)\geq\begin{cases} \frac{2}{\sqrt{-\kappa}}\sinh^{-1}\left(\sqrt{\frac{n+1}{2n}} \sinh\left(\sqrt{-\kappa}\;\mathfrak{R}(A)\right)\right),&\text{ for }\kappa<0\\ 2\mathfrak{R}(A)\sqrt{\frac{n+1}{2n}},&\text{ for }\kappa=0 \\ \frac{2}{\sqrt{\kappa}}\sin^{-1}\left(\sqrt{\frac{n+1}{2n}} \sin\left(\sqrt{\kappa}\;\mathfrak{R}(A)\right)\right), &\text{ for }\kappa>0\text{ and}\\&\mathfrak{R}(A)\in \left[0,\frac{\pi}{2\sqrt{\kappa}}\right] \end{cases} \end{equation}\]

Discussions

References

Adams, Henry, Florian Frick, Sushovan Majhi, and Nicholas McBride. 2023. “Hausdorff Vs Gromov–Hausdorff Distances.” arXiv Preprint arXiv:2309.16648.
Chazal, Frédéric, Ruqi Huang, and Jian Sun. 2015. “Gromov–Hausdorff Approximation of Filamentary Structures Using Reeb-Type Graphs.” Discrete & Computational Geometry 53 (3): 621–49. https://doi.org/10.1007/s00454-015-9674-1.
Dekster, B. V. 1997. “The Jung Theorem in Metric Spaces of Curvature Bounded Above.” Proceedings of the American Mathematical Society 125 (8): 2425–33. https://doi.org/10.1090/s0002-9939-97-03842-2.
Ge, Xiaoyin, Issam Safa, Mikhail Belkin, and Yusu Wang. 2011. “Data Skeletonization via Reeb Graphs.” In Advances in Neural Information Processing Systems, edited by J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger. Vol. 24. Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/2011/file/3a0772443a0739141292a5429b952fe6-Paper.pdf.
Hausmann, Jean-Claude. 1995. “On the Vietoris-Rips Complexes and a Cohomology Theory for Metric Spaces.” In Prospects in Topology (AM-138), 175–88. Princeton University Press.
Komendarczyk, Rafal, Sushovan Majhi, and Will Tran. 2024. “Topological Stability and Latschev-Type Reconstruction Theorems for \(\boldsymbol{\mathrm{CAT}(κ)}\) Spaces.”
Latschev, J. 2001. “Vietoris-Rips Complexes of Metric Spaces Near a Closed Riemannian Manifold.” Archiv Der Mathematik 77 (6): 522–28. https://doi.org/10.1007/PL00000526.
Majhi, Sushovan. 2023a. “Demystifying Latschev’s Theorem: Manifold Reconstruction from Noisy Data.”
arXiv:2204.14234 [Math.AT]. https://doi.org/10.48550/ARXIV.2305.17288.
———. 2023b. “VietorisRips Complexes of Metric Spaces Near a Metric Graph.” Journal of Applied and Computational Topology, May. https://doi.org/10.1007/s41468-023-00122-z.